package lucky;

import java.util.*;

public class Test {
    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 3};
        // 1.排序
        Arrays.sort(arr);
        // 2.寻找结果
        System.out.println(getLuckNum(arr, arr.length, 0, 0, 1));
    }

    private static int getLuckNum(int[] arr, int len, int pos, int sum, int multi) {
        int count = 0;
        for (int i = pos; i < len; i++) {
            sum += arr[pos];
            multi *= arr[pos];

            if (sum > multi) {
                count = count + 1 + getLuckNum(arr,len,i+1,sum,multi);
            } else if (arr[i] == 1){
                count = count + getLuckNum(arr,len,i+1,sum,multi);
            } else {
                break;
            }
            // 回溯
            sum = sum - arr[i];
            multi = multi / arr[i];
            while (i < len - 1 && arr[i] == arr[i + 1]) {
                i++;
            }
        }
        return count;
    }
}
